
/**
 * @ClassName Test
 * @Description KMP算法
 * @Author MOSS
 * @Date 2023/12/31 10:35
 * @Version 1.0
 */
public class KMP {
    /**
     *
     * @param str 主串
     * @param subStr 模式床
     * @param pos 主串开始匹配的位置
     * @return 成功匹配后主串的下标 匹配失败则返回-1
     */
    private  int nextArray[]; // 返回到的下标数组
    private void getNextArray(char [] subStr){
        int k = 0; // 回退到的下标
        nextArray[0] = -1;
        nextArray[1] = 0;
        for (int i = 2; i < subStr.length; ) {
            if(k == -1 || subStr[i-1] == subStr[k]){
                nextArray[i] = k + 1;
                i++;k++;
            }else{
                 k = nextArray[k];

            }
        }

    }
    public int KMP(char [] str , char[] subStr,int pos){
        if(str == null || subStr == null)
            return  -1;
        if(str.length == 0 || subStr.length == 0)
            return -1;
        if(pos < 0 || pos >= str.length)
            return -1;
        int j = 0;
        for (int i = pos; i < str.length; ) {
            if(j == -1 ||str[i] == subStr[j]){
                i++;
                j++;
            }else{
                nextArray = new int[subStr.length];
                getNextArray(subStr);
                j = nextArray[j];
            }
            if(j >= subStr.length)
                return i - j;
        }
        return -1;


    }
    public static void main(String[] args) {
        KMP test = new KMP();
        String a= "asdasdffas";
        String b ="daasdas";
        int ret = test.KMP(a.toCharArray(),b.toCharArray(),0);
        System.out.println(ret);

    }

}
